The present invention relates to apparatus and methods for routing packets in a packet network.
Whilst conventional routers in packet networks can forward millions of packets per second, their response to a signalling packet signalling a change in network characteristics can take more than a second. This can lead to the mis-routing of hundreds of thousands of packets—in turn possibly leading to routing loops which at best cause delay and at worst cause the packet to be dropped by the network. For some customers of network operators (e.g. financial traders running algorithmic trading systems) delay or loss of a packet can be very expensive. There is a need to speed up the process of adapting to a change in network characteristics—a process known as convergence or re-convergence in the art.
US Patent application 2011/0075680 discloses a router which includes a plurality of line cards. Each of the line cards has storage for a global Forwarding Information Base, and a complete local Forwarding Information Base which includes a copy of less than all the entries in the global Forwarding Information Base. Each line card determines how to forward packets based on the complete local Forwarding Information Base.
According to a first aspect of the present invention, there is provided a line card for use in a communications network node having a plurality of line cards in digital electronic communication with a routing processor shared by the line cards, said line card having:
one or more line interfaces for connection to communication lines in a communications network, said interfaces being arranged to receive network packets addressed to nodes in said communications network;
one or more interfaces arranged to transmit network packets processed by said line card to another of said line cards;
said line card being arranged in operation to:
i) receive network state, updates from other, routers via communications lines terminating at the line cards;
ii) pass said network state updates to the shared routing processor for input into a comprehensive routing process run by the shared routing processor which occasionally generates a set of comprehensive routes for use by the line cards; and
iii) route incoming packets on the basis of the received comprehensive set of routes;
said line card being characterised by:
being arranged to further respond to receiving a network state update by calculating one or more interim routes taking said received network state update into account, and routing incoming packets over said interim routes until the next occasion on which a comprehensive set of routes is received from said shared routing processor.
The performance of a communications network having a plurality of line cards in digital electronic communication with a routing processor shared by the line cards, in which the line cards:
i) receive network state updates from other routers via communications lines terminating at the line cards;
ii) pass said network state updates to the shared routing processor for input into a comprehensive routing process run by the shared routing processor which occasionally generates a set of comprehensive routes for use by the line cards; and
iii) route incoming packets on the basis of the received comprehensive set of routes;
is improved by arranging one or more of the line cards to further respond to receiving a network state update by running an interim routing process to generate one or more interim routes, and routing incoming packets over said interim routes until the next occasion on which a comprehensive set of routes is received. In particular, routing in reaction to a network state change is improved in that some rapid routing changes are made in reaction to the network status update before more thorough routing changes are applied.
It is to be noted that in some embodiments, the routing processor comprises one or more routing processor cards present in a router which includes the line card. In other embodiments, the routing processor comprises a control plane system shared by the routers in a communications network.
Preferably, the line card is further arranged to judge the importance of the network state update, and only run said interim routing process on said network state update being found to be important. This has the result that the extra processing required to generate interim routes is only carried out when required.
Preferably, said interim routing process generates routes for a portion of the network local to the router. This enables the accurate routing of those packets which are addressed to local nodes in the network (local nodes being a subset of the nodes in the network which are closer to the router than the remainder of nodes in the network), without the concomitant delay in calculating routes to all nodes in the network.
Preferably, the line card has bespoke hardware configured to perform said interim routing process. The bespoke hardware might comprise a field programmable gate array programmed to perform said interim routing process. This is faster than using a general purpose microprocessor, but maintains some programmability. In other embodiments, the bespoke hardware might comprise an application-specific integrated circuit. Again, this is faster than using a general purpose microprocessor.